/**
 * Leetcode 307. Range Sum Query - Mutable
 * https://leetcode.com/problems/range-sum-query-mutable/description/
 *
 * @author Kevin
 * @date 2018-12-25
 */
public class NumArray3 {

    /**
     * 求和数列
     * <p>
     * 思路：
     * sum[i]存储前i个元素和, sum[0] = 0
     * 即sum[i]存储nums[0...i-1]的和
     * sum(i, j) = sum[j + 1] - sum[i]
     */
    private int[] sum;

    private int[] data;

    public NumArray3(int[] nums) {
        this.data = new int[nums.length];
        for (int i = 0; i < nums.length; i++) {
            this.data[i] = nums[i];
        }

        this.sum = new int[nums.length + 1];
        this.sum[0] = 0;
        for (int i = 1; i < this.sum.length; i++) {
            this.sum[i] = this.sum[i - 1] + nums[i - 1];
        }
    }

    /**
     * 求区间内的和
     *
     * @param i
     * @param j
     * @return
     */
    public int sumRange(int i, int j) {
        return sum[j + 1] - sum[i];
    }

    /**
     * 根据索引修改对应的值
     *
     * @param index
     * @param val
     */
    public void update(int index, int val) {
        this.data[index] = val;
        for (int i = index + 1; i < sum.length; i++) {
            sum[i] = sum[i - 1] + data[i - 1];
        }
    }

    public static void main(String[] args) {
        int[] nums = {1, 3, 5};
        NumArray3 numArray = new NumArray3(nums);
        System.out.println(numArray.sumRange(0, 2));
        numArray.update(1, 2);
        System.out.println(numArray.sumRange(0, 2));
    }

}
